// 线索二叉树
//>>>>>>>>>>>>>>>>>>>>>>>>>引入头文件<<<<<<<<<<<<<<<<<<<<<<<<<<<<

#include <stdio.h>       //使用了标准库函数 
#include <stdlib.h>      //使用了动态内存分配函数 
#include <windows.h>
//>>>>>>>>>>>>>>>>>>>>>>>自定义符号常量<<<<<<<<<<<<<<<<<<<<<<<<<< 

#define OVERFLOW -2          //内存溢出错误常量
#define TRUE 1               //表示逻辑真的常量 

//>>>>>>>>>>>>>>>>>>>>>>>自定义数据类型<<<<<<<<<<<<<<<<<<<<<<<<<<

typedef char TElemType;
typedef int Status;

//定义NIL为空格 
TElemType NIL = ' ';

//------------------- 二叉树的二叉线索存储表示 --------------------
//采用枚举类型定义指针标志位 
typedef enum{
	Link,   //Link(0)：  指针 0，表示左右指针就是指向左右孩子
	Thread  //Thread(1)：线索 1，表示左指针指向前驱线索，右指针指向后续线索
}PointerTag; 

typedef struct BiThrNode{
	TElemType data;                     //数据域，存储节点数据 
	struct BiThrNode *lchild, *rchild;  //左右孩子指针
	PointerTag LTag, RTag;              //左右标志
}BiThrNode, *BiThrTree;

//---------------------------线索二叉树操作---------------------------- 

/*
	函数：创建二叉树
	参数：BiThrTree &T 线索二叉树的引用 
	返回值：状态码，操作成功返回OK，否则返回ERROR 
	作用：按先序输入线索二叉树中结点的值，构造线索二叉树T。
	      空格表示空结点
*/
void CreateBiThrTree(BiThrTree &T) {
	
	//保存从键盘接收的字符 
	TElemType ch;
	scanf("%c", &ch);
	
	//若输入了空格，则此节点为空 
	if(ch == NIL) {
		T = NULL;	
	}else{ //若输入的不是空格则创建新结点并添加到线索二叉树的合适位置 
		//申请根结点存储空间 
		T = (BiThrTree)malloc(sizeof(BiThrNode));
		
		//检查空间分配是否成功 
		if(!T) { 
			exit(OVERFLOW);
		}
		
		//给根结点赋植
		T->data = ch;
		
		//递归地构造左子树
		CreateBiThrTree(T->lchild);
		
		T->LTag = Link; 
		
		//递归地构造右子树
		CreateBiThrTree(T->rchild);
		
        T->RTag = Link;
	}
}

/*
	函数：Print
	参数：TElemType c 被访问的元素 
	返回值：状态码，操作成功返回OK，操作失败返回ERROR 
	作用：访问元素e的函数，通过修改该函数可以修改元素访问方式，
	      该函数使用时需要配合遍历函数一起使用。 
*/
void Print(TElemType c){
	
	//以控制台输出的方式访问元素 
   	printf(" %c ", c);
}

//---------------------------- 中序线索化 --------------------------- 

//全局变量，始终指向刚刚访问过的结点
BiThrNode* pre = NULL;

/*
	函数：InThreading
	参数：BiThrTree p 指向线索二叉树结点的指针p 
	返回值：无
	作用：通过中序遍历递归地对头结点外的其他结点进行中序线索化，
	      线索化之后pre指向最后一个结点。
	      此函数会被InOrderThreading函数调用。  
*/
void InThreading(BiThrNode* p) {
	if(p->lchild == NULL){
        p->lchild = pre;
        p->LTag = Thread;
    }

    if(pre != NULL && pre->rchild == NULL){
        // 建立前驱结点的后继线索
        pre->rchild = p;
        pre->RTag = Thread;
    }
    pre = p;
}
/*
	函数：中序线索化
	参数：BiThrTree &Thrt 头结点的引用 
	      BiThrTree T 指向线索二叉树根结点的指针，因为不改变T所以不需要引用
	返回值：状态码，操作成功返回OK，否则返回ERROR 
	作用：中序遍历二叉树T，并将其中序线索化。
*/
void InOrderThreading(BiThrTree &T) {
    if(T != NULL){
        InOrderThreading(T->lchild);
        InThreading(T);
        InOrderThreading(T->rchild);
    }
}
/*
	函数：InOrderTraverse_Thr
	参数：BiThrTree T 指向线索二叉树根结点的指针
	      Status(*Visit)(TElemType) 函数指针，指向元素访问函数 
	返回值：状态码，操作成功返回OK，否则返回ERROR 
	作用：中序遍历线索二叉树T(头结点)的非递归算法。
*/
void InOrderTraverse_Thr(BiThrTree T) {
    //找到最左边的第一个被遍历的结点
    while(T->lchild != NULL){
        T = T->lchild;
    }
    while(T != NULL){
        Print(T->data);
        if(T->RTag == Link){
            T = T->rchild;
            while(T->LTag == Link){
                T = T->lchild;
            }
        }else{
            T = T->rchild;
        } 
    }
}

/**
 *  前序线索化
*/
void preThreading(BiThrNode* p){
	if(p->lchild == NULL){
		p->LTag = Thread;
		p->lchild = pre;
	}
	if(pre != NULL && pre->rchild == NULL){
		pre->RTag = Thread;
		pre->rchild = p;
	}
	pre = p;
}
void preOrderThreading(BiThrTree &T) {
	if(T != NULL){
		preThreading(T);
		if(T->LTag == Link){
			preOrderThreading(T->lchild);
		}	
		if(T->RTag == Link){
			preOrderThreading(T->rchild);
		}		
	}
}
void preOrderTraverse_Thr(BiThrTree T) {
	while(T != NULL){
		Print(T->data);
		if(T->LTag == Link){
			T = T->lchild;
		}else{
			T = T->rchild;
		}
	}
}

/**
 *  后序线索化
*/
void postThreading(BiThrNode* p){
	if(p->lchild == NULL){
		p->LTag = Thread;
		p->lchild = pre;
	}
	if(pre != NULL && pre->rchild == NULL){
		pre->RTag = Thread;
		pre->rchild = p;
	}
	pre = p;
}
void postOrderThreading(BiThrTree &T) {
	if(T != NULL){
		postOrderThreading(T->lchild);
		postOrderThreading(T->rchild);
		postThreading(T);		
	}
}
void postOrderTraverse_Thr(BiThrTree T) {
    //找到最左边的第一个被遍历的结点
    while(T->lchild != NULL){
        T = T->lchild;
    }
    while(T != NULL){
        Print(T->data);

    }
}

/*
	函数：DestroyBiTree
	参数：BiThrTree &T T指向线索二叉树根结点 
	返回值：状态码，操作成功返回OK，否则返回ERROR 
	作用：递归地销毁线索二叉树，被DestroyBiThrTree函数调用。 
*/
void DestroyBiTree(BiThrTree &T) {
	
	//非空树
	if(T) { //if(T) <=> if(T != NULL) 
		
		//如果有左孩子则递归地销毁左子树
		if(T->LTag == Link) {
			DestroyBiTree(T->lchild);
		}
	   
	   	//如果有右孩子则递归地销毁右子树
		if(T->RTag == Link) {
			DestroyBiTree(T->rchild);
		} 
	   
	   	//释放根结点
		free(T);
		
		//指针置空 
		T = NULL;
	}
	
}

/*
	函数：DestroyBiTree
	参数：BiThrTree &Thrt Thrt指向线索二叉树头结点 
	返回值：状态码，操作成功返回OK，否则返回ERROR 
	作用：若线索二叉树Thrt存在，递归地销毁线索二叉树Thrt。 
*/
void DestroyBiThrTree(BiThrTree &Thrt) {
	
	//头结点存在
	if(Thrt) {
		
		//若根结点存在，则递归销毁头结点lchild所指的线索二叉树 
		if(Thrt->lchild) { //if(Thrt->lchild) <=> if(Thrt->lchild != NULL)
			DestroyBiTree(Thrt->lchild);
		}
		
		//释放头结点
		free(Thrt);
		
		//线索二叉树Thrt指针赋0
		Thrt = NULL;
	}
	
}

int main(int argc, char** argv) {
	system("chcp 65001 > nul");
	printf("---------------------线索二叉树测试程序-----------------------\n");
	
	BiThrTree T;
	
	//使用用户输入的先序遍历序列生成一棵没有被线索化的二叉树 
	printf("请按先序遍历顺序输入二叉树，空格表示空子树，输入完成后按回车确认\n");
	CreateBiThrTree(T);
	
	// //在中序遍历过程中线索化二叉树
	// InOrderThreading(T);
	// if(T->rchild == NULL){
	// 	pre->RTag = Thread ;
	// }
	// printf("中序遍历线索二叉树:\n");
	// InOrderTraverse_Thr(T);
	// printf("\n");

	// //前序遍历过程种线索化二叉树
	preOrderThreading(T);
	pre->RTag = Thread ;
	pre->rchild = NULL;
	printf("前序遍历线索二叉树:\n");
	preOrderTraverse_Thr(T);
	printf("\n");

	//后序遍历过程种线索化二叉树
	// postOrderThreading(T);
	// pre->RTag = Thread ;
	// pre->rchild = NULL;
	// printf("无法使用后序迭代遍历线索二叉树:\n");
	// postOrderTraverse_Thr(T);
	// printf("\n");

	//销毁线索二叉树
	DestroyBiThrTree(T);
}

/*
---------------------线索二叉树测试程序-----------------------
请按先序遍历顺序输入二叉树，空格表示空子树，输入完成后按回车确认
ABE*F**C*DGHI*J*K******↙   
    //说明：此处的*是空格，为方便确认输入了几个空格将空格替换成*，测试输入时请将*改回空格
	        ↙表示回车确认    输入（可直接复制，不要复制↙）：ABE F  C DGHI J K      ↙
先序遍历递归  算法结果： A  B  E  F  C  D  G  H  I  J  K

中序遍历递归  算法结果： E  F  B  C  I  J  K  H  G  D  A

后序遍历递归  算法结果： F  E  K  J  I  H  G  D  C  B  A

--------------------------------
Process exited with return value 0
Press any key to continue . . .
*/
